package introduction;

import java.util.*;

import javax.print.attribute.standard.Finishings;
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
public class chapter41 {
	
	public static void main(String []args){
		int a[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
		Data d=new Data(0,0,0);
		chapter41 c=new chapter41();
		d=c.find_maxsum_sub(a, 0, a.length-1);
		System.out.println(d.max_left+" "+d.max_right+" "+d.sum);
	
	}
	
Data find_maxsum_sub(int a[],int low,int high){
	int mid;
	Data d1=new Data(0, 0, 0);
	Data d2=new Data(0, 0, 0);
	Data d3=new Data(0, 0, 0);
	if (low==high)
	{System.out.println("wrong");
	return null;}
	
	else {mid=(low+high/2);
	d1=find_maxsum_sub(a,low,mid);
	d2=find_maxsum_sub(a, mid+1, high);
	d3=find_maxcross_sub(a, low, high);
	
	if ((d1.sum>d2.sum)&&(d1.sum>d3.sum))
			return d1;
	else if ((d2.sum>d1.sum)&&(d2.sum>d3.sum))
			return d2;
	else return d3;
	
}
}

Data find_maxcross_sub(int a[],int low,int high){
	int mid=low+high/2;
	int leftsum=-100000;
	int rightsum=-100000;
	int sum=0;
	int leftmax = 0,rightmax = 0;
	Data data =new Data(0,0,0);
	
	for(int i=mid;i>low;i--){
		sum=sum+a[i];
		if(sum>leftsum){
			leftmax=i;
			leftsum=sum;
		}
	}
	
	for(int j=mid+1;j<high;j++){
		sum=sum+a[j];
		if(sum>leftsum){
			rightmax=j;
			rightsum=sum;
		}
	}
	
	data.max_left=leftmax;
	data.max_right=rightmax;
	data.sum=leftsum+rightsum;
	
	return data;
	
}

}
class Data{
	int max_left;
	int max_right;
	int sum;
	Data(int a,int b,int c){
		this.max_left=a;
		this.max_left=b;
		this.sum=c;
	}
}